package maximumSubarray;



public class Solution {
    public int maxSubArray(int[] nums) {
        return solve(nums,0,nums.length-1);
    }

	private int solve(int[] nums, int left, int right) {
		if (left==right) return nums[left];
		int mid=left+(right-left)/2;
		int leftMax=solve(nums, left, mid);
		int rightMax=solve(nums, mid+1, right);
		int leftSum=Integer.MIN_VALUE,rightSum=Integer.MIN_VALUE,temp=0;
		for (int i=mid;i>=left;i--){
			temp=temp+nums[i];
			leftSum=Math.max(leftSum, temp);
		}
		temp=0;
		for (int i=mid+1;i<=right;i++){
			temp=temp+nums[i];
			rightSum=Math.max(rightSum, temp);
		}
		return (Math.max(leftSum+rightSum, Math.max(leftMax, rightMax)));
		
	}
	public static void main(String args[]){
		Solution so=new Solution();
		int[] nums={8,-19,5,-4,20};
		System.out.println(so.maxSubArray(nums));
		}
}
/* 
 * 53. Maximum Subarray
 * 题目大意：长度为n的数组，取出其中一段连续的数，求最大和（至少取一个数）
 * O（n）解：DP解 f[i]表示以nums[i]为结尾的序列的最大和
 * 状态转移方程f[i]=max(f[i-1]+nums[i],nums[i])
 * 
 * O(nlogn)解：分治法
 * 对于长度为n的序列，其最大子序列有三种情况
 * I.最大序列出现在[0,mid]
 * II.最大序列出现在[mid+1,n]
 * III.最大序列为[i,j]（0<=i<=mid,mid+1<=j<=n)
 * 所以对三种情况进行递归
 * 得解
 */